package leetCode.solution;

/**
 * 给定一个二叉树，我们在树的节点上安装摄像头。
 * 
 * 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
 * 
 * 计算监控树的所有节点所需的最小摄像头数量。
 * 
 * @author jerry
 * @ClassName: Solution968
 * @Description:TODO(描述这个类的作用)
 * @date 2023年1月9日 下午3:34:14
 */
public class Solution968 {
	public int minCameraCover1(TreeNode root) {
		Info rootInfo = process(root);
		return State.UNCOVER.equals(rootInfo.getState())?rootInfo.size+1:rootInfo.size;
	}
	
	
	public int minCameraCover(TreeNode root) {
		Info rootInfo = process(root);
		return State.UNCOVER.equals(rootInfo.getState())?rootInfo.size+1:rootInfo.size;
	}
	// 不考虑孙子，孙子默认是cover的
	private Info process(TreeNode root) {
		if(root==null) {
			return new Info(State.COVERDNOCAMERA, 0);
		}
		
		Integer size = 0;
		
		// 贪心，未统计儿子的所有三种情况
		Info leftInfo = process(root.left);
		Info rightInfo = process(root.right);
		size = leftInfo.getSize() + rightInfo.getSize();
		
		// 儿子有uncover的
		if(State.UNCOVER.equals(leftInfo.getState()) || State.UNCOVER.equals(rightInfo.getState())){
			return new Info(State.COVERDHASCAMERA, size+1);
		}
		
		//儿子都cover，且有放相机的
		if(State.COVERDHASCAMERA.equals(rightInfo.getState()) || State.COVERDHASCAMERA.equals(leftInfo.getState())) {
			return new Info(State.COVERDNOCAMERA, size);
		}
		
		// 儿子都cover，且都没放相机
		return new Info(State.UNCOVER, size);
	}
	
	class Info{
		State State;
		Integer size;
		public Info(State State, Integer size) {
			super();
			this.State = State;
			this.size = size;
		}
		public State getState() {
			return State;
		}
		public void setState(State State) {
			this.State = State;
		}
		public Integer getSize() {
			return size;
		}
		public void setSize(Integer size) {
			this.size = size;
		}
		
	}
	
	enum State{
		 /**
	     * 未被覆盖
	     */
	    UNCOVER,
	    /**
	     * 被覆盖有相机
	     */
	    COVERDHASCAMERA,
	    /**
	     * 被覆盖无相机
	     */
	    COVERDNOCAMERA
	}

	class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}
}
